package com.hr.tuling.list;

/**
 * @author ：zhz
 * @date ：Created in 2020/12/23
 * @version: V1.0
 * @slogan: 天下风云出我辈，一入代码岁月催
 * @description: 环形单链表的约瑟夫问题
 **/
public class Josephus {
    public static void main(String[] args) {
        // 创建一个环形单链表
        Node lastNode = new Node(10);
        Node node9 = new Node(9, lastNode);
        Node node8 = new Node(8, node9);
        Node node7 = new Node(7, node8);
        Node node6 = new Node(6, node7);
        Node node5 = new Node(5, node6);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node headNode = new Node(1, node2);
        lastNode.next = headNode;
        // 执行约瑟夫方法
        josephus(headNode, lastNode, 10, 2, 3);
    }

    /**
     * 约瑟夫问题
     *
     * @param headNode 环形单链表的首节点
     * @param lastNode 环形单链表的尾节点
     * @param size     环形单链表中节点的个数
     * @param start    从编号为 start 的小孩开始报数
     * @param count    每次数几下
     */
    private static void josephus(Node headNode, Node lastNode, int size, int start, int count) {
        // 1.处理不合法的情况
        // 1.1 处理 headNode 为 null 的情况
        if (headNode == null) {
            throw new NullPointerException("headNode 为 null");
        }
        // 1.2 处理 start 和 count 不合法的情况
        if (start > size || count > size) {
            throw new IllegalArgumentException("参数不合法");
        }
        // 2.设置编号为 start 的小孩开始报数，并且使用 headNode 指向该节点
        for (int i = 0; i < start - 1; i++) {// 把 headNode 和 lastNode 往后移动 start-1 次
            headNode = headNode.next;
            lastNode = lastNode.next;
        }
        // 3.定义一个循环，用于循环的执行报数操作
        while (size != 0) { // 如果 size 等于 0，则停止报数
            // 4.执行报数操作，也就是找到需要出圈的小孩，我们使用 headNode 指向需要出圈的节点
            // 把 headNode 和 lastNode 往后移动 count-1 次
            for (int i = 0; i < count - 1; i++) {
                headNode = headNode.next;
                lastNode = lastNode.next;
            }
            // 5.输出需要出圈小孩的编号，也就是输出 headNode 保存的数据值
            System.out.println(headNode.data);
            // 6.实现小孩的出圈操作，也就是把 headNode 从环形单链表中删除
            // 6.1 获得删除节点的后一个节点
            Node nextNode = headNode.next;
            // 6.2 设置 lastNode 的 next 值为 nextNode
            lastNode.next = nextNode;
            // 6.3 设置 headNode 的 next 值为 null
            headNode.next = null;//促进gc
            // 7.更新 size 的值
            size--;
            // 8.设置 headNode 指向 nextNode
            headNode = nextNode;
        }


    }


    /**
     * 节点类
     */
    private static class Node {
        /**
         * 用于保存节点中的数据值
         */
        private Object data;
        /**
         * 用于保存下一个节点的地址值
         */
        private Node next;

        /**
         * 专门为 data 做初始化的工作
         *
         * @param data
         */
        public Node(Object data) {
            this.data = data;
        }

        /**
         * 专门为 data 和 next 做初始化的工作
         *
         * @param data
         * @param next
         */
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

}
